２進分数を使用した効率的な拡散ディザリング

专利摘要:
拡散ディザリングは、１つ以上のシフト、加算、および／または、減算の演算を有する、１組の拡散フィルタ重みを適用することによって、効率的に実行できる。既存の拡散フィルタを、２進分数で近似することができ、これによって、フィルタ重みを適用する際の除算演算を、ビットシフト演算で実行できるようにする。１組のフィルタ重みと、ピクセル誤差との積を計算するためのアルゴリズムが識別され、アルゴリズムは、１つ以上のシフト、加算、または、減算の演算を使用して、計算を実行する。演算の組み合わせの網羅的なサーチを行って、積を計算するための効率的なアルゴリズムを見つけることができる。
公开号:JP2011507409A
申请号:JP2010538185
申请日:2008-12-12
公开日:2011-03-03
发明作者:レズニク、ユリー
申请人:クゥアルコム・インコーポレイテッドＱｕａｌｃｏｍｍ Ｉｎｃｏｒｐｏｒａｔｅｄ；
IPC主号:H04N1-405

专利说明:

[0001] ここでの主題は、一般的に画像処理に関連する。より詳細には、主題は、その重みが２進分数であるフィルタを使用して、効率的に拡散ディザリングを実行することと、１つ以上のシフト、加算、または、減算演算を使用して、重みを適用することとに関連する。]
背景

[0002] 有限のカラーパレットを有するシステム中で、画像が表現されることになるとき、オリジナル画像のカラーを表現するために、パレットからカラーが選択される。有限なパレットはギャップを持つので、オリジナル画像の本当のカラーは、パレット中のどのカラーにも、正確には対応していないかもしれず、選択されたカラーは、本当の色を、パレット中の近似の色に丸めることによって、選ばれるかもしれない。選択されたカラーが、オリジナル画像の本当のカラーとは異なっているという点で、丸め誤差が認識される。拡散ディザリングを使用して、あるピクセル中の誤差を、隣接または近隣のピクセルへと分配でき、これによって、アーティファクト、または、そうでなければ丸め誤差によってもたらされるであろう、他の歪みを減少させる。]
[0003] 拡散ディザリングは、あるピクセルに対する丸め誤差に対して、フィルタを適用することと、フィルタにしたがって、誤差を分配することとによって実行される。フィルタは、重みと呼ばれる、１組の端数を有する。丸め誤差の一部を、他のピクセルに分配するために、フィルタ中のそれぞれの重みは、誤差によって乗算され、結果としての積が、そのカラー値が丸められているピクセルの近隣の特定のピクセルに対して分配される。端数の重みを適用することは、一連の乗算および除算演算、または、浮動小数点算術を使用して、通常は実行され、これは、計算的にコストが高い。]
[0004] 良好な画像結果を生み出すために、さまざまなフィルタが、実験的に決定されてきたが、これらのフィルタの多くが、適用するのが複雑である端数重みを使用していた。例えば、Ｓｔｕｃｋｉフィルタは、その分母が４２である端数を使用し、Ｊａｒｖｉｓフィルタは、その分母が４８である端数を使用する。分母が２の累乗であるとき、分子によって誤差を乗算して、次に、高速右ビットシフト演算を使用して、分子によって除算することによって、端数を誤差に適用できる。しかしながら、４２および４８は、２の累乗ではないので、これらの分母を有する端数を適用することは、機械の除算ロジック、または、浮動小数点乗算のいずれかを使用することを含み、これらの両方は、計算的にコストが高い。さらに、端数中の分子を重みに適用することは、乗算演算を含んでいてもよく、これは、シフト、加算、または、減算の演算ほど効率的ではない。ワイヤレスハンドセット、または、ハンドヘルドコンピュータのような小型の装置上では、これらのコストの高い演算を使用して、許容可能な速度で、拡散ディザリングを実行するための十分な計算パワーがないかもしれない。]
概要

[0005] 拡散ディザリングは、１つ以上のシフト、加算、または、減算の演算を使用して、ピクセル誤差に対して、拡散フィルタ重みを適用することによって、効率的に実行できる。その端数が２進分数である、すなわち、その分母が２の累乗である端数である、フィルタを選択できる。さらに、一連の左シフト、加算、および／または、減算の演算を使用して、ピクセル誤差に対して、端数中の分子を適用するアルゴリズムを識別できる。左シフト、加算、および／または、減算の演算を使用して、ピクセル誤差によって、分子を乗算し、右シフトを使用して、結果を２の累乗の分母によって除算して、誤差に対して、重みを効率的に適用することを可能にする。]
[0006] ２進分数である重みを有するフィルタが、知られているフィルタ中の重みを近似する２進分数を使用することによって作成できる。別の例として、２つ以上の知られているフィルタが、それぞれのフィルタの所定の位置における重みの算術平均をとることによって結合でき、次に、２進分数を使用して、結果としての平均を近似してもよい。これらの技術、または、他の技術を使用して、その重みが２進分数であるフィルタを作成できる。]
[0007] フィルタ重み中の分子を、ピクセル誤差に対して適用することによって、アルゴリズムを作成または識別することができる、アルゴリズムは、１つ以上のシフト、加算、および／または、減算の演算を使用して、重みを適用する。アルゴリズムを作成する１つの方法は、ベース値を持つディクショナリとともに開始し、次に、ディクショナリが、フィルタ中の分子として使用されるすべての係数に到達できる演算を含むまで、ディクショナリに異なるシフト、加算、および、減算の演算を加えることである。次に、ディクショナリのコンテンツは、アルゴリズムとして保存される。同一の組の係数を発生させる異なるアルゴリズムが作成できる。これらのアルゴリズムは、効率性に関して比較されることができ、特定の効率性基準を満たすアルゴリズムを使用して、誤差値に対してフィルタ重みを適用するプロセスを実現できる。]
[0008] この概要は、以下で詳細な説明においてさらに開示する概念の、簡潔化した形態で、概念の選択を紹介するように提供する。この概要は、特許請求の範囲の主題のキーとなる特徴、もしくは、本質的な特徴を識別することを意図しておらず、または、特許請求の範囲の主題の範囲を制限するのに使用されることを意図していない。]
図面の簡単な説明

[0009] 図１は、ディザリングフィルタを見つけて、適用する例示的なプロセスのフロー図である。
図２は、２進分数を計算して、フィルタ中の重みを近似する例示的なプロセスのフロー図である。
図３は、例示的なアルゴリズムにおける従属性のグラフである。
図４は、例示的な配列のブロック図である。
図５は、図４の配列におけるエレメントとして使用されてもよい例示的なデータ構造のブロック図である。
図６は、アルゴリズムを発生させる例示的なプロセスのフロー図である。
図７は、例示的なワイヤレスデバイス、または、端末の構成のブロック図である。] 図１ 図２ 図３ 図４ 図５ 図６ 図７
発明の詳細な説明

[0010] デジタルイメージングにおいて、カラーは、有限カラーパレットへと量子化される。例えば、イメージングスキームが、あるピクセルのカラーを表現するのに８ビットを割り当てる場合、ピクセルは、２５６（２8）の異なるカラーのうちの１つをとることができるが、個別の２５６カラーの間の中間値をとることはない。ハンドヘルドコンピュータ、および、ワイヤレス電話機のような、多くの電子的デバイスは、小さいカラーパレットを採用している。いくつかのケースにおいて、これらのデバイスは、４ビットのカラー深度（すなわち、カラーパレットのサイズ）を有するイメージングスキームを採用し、これは、あるピクセルにおける、２4（＝１６）の異なるカラーの表現を可能にする。しかしながら、現実の世界の画像は、カラーにおける任意の小さい濃淡または変動を呈する。高解像度デジタル写真でキャプチャされた画像は、量子化されたカラーパレットを持っていてもよいが、表現可能なカラー中の濃淡は、非常に細かくてもよく、画像が表示されることになるプラットフォームよりずっと小さくてもよい。したがって、ソース画像が、現実の世界の画像、または、高カラー深度でキャプチャされた画像であり、ターゲットイメージングシステムが、比較的粗いカラーパレットを有しているとき、カラー値は、パレットの制約内にフィットするように、切り上げられることができ、または、切り捨てることができる。]
[0011] カラーが切り上げられ、または、切り捨てられるとき、誤差が認識される。したがって、イメージングシステムが、整数０から１５によって表現される、１６のカラーを用いており、特定のピクセルが、ソース画像を正確に表現するために、１４．３にセットされるべきであるとしてシステムが決定する場合、システムは、カラーを、１４．３から１４に切り捨てることができる。この丸めることは、ターゲットピクセルのカラー値が、０．３だけソース画像から異なることをもたらし、したがって、ターゲットピクセル中の誤差は、０．３である。丸めることに対処しようと試みることなく、誤差を無視して、丸められた値を単に受け入れることも可能である。このケースでは、ターゲット画像中のカラーが、０．３だけソース画像中のカラーとは異なるという事実は、情報の損失となる。ターゲット画像の品質に対する期待が低い場合、この情報の損失は受入可能であるかもしれない。しかしながら、いくつかのケースでは、情報の損失は、深刻なことであるかもしれない。例えば、ターゲット画像スキームが、２カラー、すなわち、白黒のカラーパレットを持っており、ソース画像が一様に、５１％グレーである場合、丸めることは、ターゲット画像中の各ピクセルが、全体的に黒く見えることをもたらすだろう。いくつかの方法で、丸め誤差に対処することは、遠くから画像を見たときに、画像がグレーに見えるように、いくつかのピクセルを黒にセットし、他のピクセルを白にセットすることを可能にする。]
[0012] 誤差に対処する1つの方法は、拡散ディザリングとして知られている技術である。拡散ディザリングは、ある割合にしたがって、丸め誤差を、隣接または近隣のピクセルに分散させることによって、丸め誤差に対処する。さまざまな拡散ディザリングがあり、これは、良好な結果を生み出すために、実験的に決定されてきた。これらのディザは、調べられているピクセルから誤差を分散させる場所と、どれほどの量において、その誤差が各ピクセルに対して分散されるかに基づいて、記述される。例えば、１つの拡散ディザリング−（作者の名前にちなんで名づけられた）Ｆｌｏｙｄ−Ｓｔｅｉｎｂｅｒｇフィルタは、以下のように記述することができる。]
[0013] 画像は、行ごとに調べられることができ、ここで、各行は、左から右に調べられ、複数の行は、上から下に調べられる。表１中の“＊”シンボルは、調べられているピクセルを表す。“＊”シンボルのすぐ横の分数は、隣接ピクセルに分配された丸め誤差の比率（すなわち、“重み”）を表す。例えば、“＊”におけるピクセルが、１４．３であり、１４に丸められている場合、そのピクセル中の合計誤差は、０．３である。その誤差の７／１６（０．３×７／１６＝．１３１２５）が、１列右側の同じ行中のピクセルに対して、分配され、誤差の１／１６が、１列右側の１列下のピクセルに対して分配される等、“＊”（現在の）ピクセル中の全体の誤差が、他のピクセルに分配されるまで行われる。したがって、ターゲット画像中で、所定のピクセルに対するカラー値は、ソース画像中の対応するピクセルのカラーと、近接ピクセル中で、カラー値を丸めることが、どれほど多く発生したかとの両方によって、決定される。各行は、左から右に調べられてもよい。あるいは、行は、蛇行するパターンで、各連続的な行で、左から右と、右から左を交互に、調べられてもよく、このケースでは、表１に示した重みのパターンは、右から左に調べられる行に対して水平に反転される。]
[0014] 効率性の見地から、Ｆｌｏｙｄ−Ｓｔｅｉｎｂｅｒｇフィルタは、重み中の分母が、２の累乗（＝２4）であるという特性を持つ。（フィルタ中のすべての分数の合計が全部で１になるように、分数における分母（１６）は、分子の合計（３＋５＋１＋７＝１６）である。）コンピューティングデバイスは、２の累乗による除算を効率的に実行でき、なぜならば、ベース２において、２の累乗による除算は、数のバイナリ表現を、除数中の指数に等しいビットの数だけ、右シフトすることによって実行できるためである。したがって、２進数Ａを、２nによって除算することになる場合、この演算は、Ａを、ｎビットだけ右シフトすることによって実行することができる。（商における分数の量は、レジスタの最後においてシフトオフされ、破棄される；したがって、この方法による除算は、商を、次の最も低い整数へと切り捨てる。）１６（＝２4）による除算は、例えば、４ビットだけ右シフトすることによって達成されることができ、この右シフトは、通常、レジスタ内で直接実行することができるネイティブ機械命令によって実行される。（この例において、標準的な意味で“右”を使用し、ここで、最小桁のビットは、“右”にあるとして考えられる。しかしながら、数の任意の表現を使用できる。シフトを記述する際の利便性のために、“右”および“左”は、標準的な右および左を指し、ここで、数が、どのように物理的に表現されるかに関わらず、最小桁のビットは、“右”に向かっているとして記述し、最上位ビットは、“左”に向かっているとして記述する。）]
[0015] Ｆｌｏｙｄ−Ｓｔｅｉｎｂｅｒｇディザリングが、（Ｂｕｒｋｅｓフィルタ、およびＳｉｅｒｒａ３フィルタのような、何らかの他の知られているフィルタがそうであるように、）２の累乗である除数を使用する一方で、重み中の分母が、２の累乗でない、他のディザリングも考えられてきた。例えば、Ｓｔｕｃｋｉフィルタを表２に示す。]
[0016] より複雑な誤差の分配を用いる、Ｓｔｕｃｋｉフィルタのようなフィルタは、何らかの状況において、Ｆｌｏｙｄ−Ｓｔｅｉｎｂｅｒｇフィルタのような、より簡潔なフィルタより良いディザリング結果を生み出してもよい。しかしながら、計算の複雑さによって、コストは高い。Ｆｌｏｙｄ−Ｓｔｅｉｎｂｅｒｇフィルタにおいてと同様に、Ｓｔｕｃｋｉフィルタ中の重みの合計は、合わせて１になる。フィルタ中の分数中の分子が、合わせて４２になるので、各分数における分母は４２である。４２は、２の累乗でないので、これらの分数を、実際の誤差値に適用することは、４２による除算を含み、これは、簡潔なビットの右シフトではなく、除算演算を通して実行される。除算演算が、処理ハードウェア中に組み込まれるか、または、ソフトウェアで実現されるかに関わらず、除算演算は、右シフトより計算的にコストが高い。]
[0017] 右シフト演算を、除算に対して使用できるようにするために、２進分数（または、２進端数）−すなわち、２の累乗である分母を持つ１組の端数−を使用して、フィルタ中の重みを近似することが可能である。拡散ディザリングフィルタ中の重みを近似する技術は、図２に関連して以下で記述する。しかしながら、誤差値に重みを適用することは、除算だけでなく、乗算も含み−すなわち、分子が重みによって乗算され、結果が分母によって除算され、−この乗算演算は、計算における非効率性の別のソースとなりかねない。２の累乗による乗算は、左シフト演算とともに、コストをかけずに実行できるが、２の累乗でない数による乗算は、計算的にコストの高い乗算ロジックを含む。Ｓｔｕｃｋｉフィルタのような、いくつかのフィルタは、２の累乗である分子を持ち、このことは、フィルタ重みを誤差値に適用する乗算ステージを簡潔にする。しかしながら、（Ｆｌｏｙｄ−Ｓｔｅｉｎｂｅｒｇフィルタのような、）いくつかのフィルタは、２の累乗でない重みを持つ。他のケースでは、２の累乗の分子を持つ（Ｓｔｕｃｋｉフィルタのような）フィルタは、２進分数で近似するとき、２の累乗でない分子を持つかもしれない。例えば、Ｓｔｕｃｋｉフィルタを、その分母が６４である端数で近似しようとする場合、端数、１／４２、２／４２、４／４２、および、８／４２は、２／６４、３／６４、６／６４、および、１２／６４として近似されるだろう。これらの分子のうちで、２は２の累乗であるが、３、６、および１２はそうではない。シフト、加算、および、減算は、計算的にコストが高くない演算である。したがって、一連のシフト、加算、および、減算を使用して、誤差値によって、重み分子を乗算するアルゴリズムを作成することによって、効率性が実現される。] 図２
[0018] ここで、図面を参照して、図１は、プロセス１００のステージを示し、ここで、ディザリングフィルタの２進近似が見つけられ、適用される。１０２において、その重みが２進分数であるフィルタが見つけられる。このようなフィルタを見つけるための１つの方法は、２の累乗を選択し、知られているフィルタ（例えば、Ｓｔｕｃｋｉフィルタ）中の各端数を、その分子が選択された２の累乗である別の端数によって、近似することである。したがって、数６４（＝２6）が選択される場合、フィルタ中の各端数は、その数で乗算できる。オリジナルフィルタ中の端数と、選択された数との積は、オリジナルの端数を近似する新しい端数の分子を与えるだろう。例えば、Ｓｔｕｃｋｉフィルタは、端数８／４２を含む。６４によって乗算されたその端数は、５１２／４２に等しく、これは、最も近い整数に丸められ、１２である。したがって、１２は、２進分数１２／６４（＝０．１８７５）中の分子である。オリジナルの端数８／４２は、ほぼ０．１９０４７６に等しく、したがって、１２／６４は、オリジナルの端数の理にかなった近似である。より高い２の累乗を分母として使用することと、その２の累乗に基づいて、端数の近似を発生させることによって、より正確な近似を得ることができる。１つの例において、何らかの範囲−例えば、２2から２10におけるすべての２の累乗に基づいて、フィルタ中で端数を近似するように、プログラムを書くことができる。加えて、上記の例は、Ｓｔｕｃｋｉフィルタのような、知られているフィルタ中の端数を近似する一方で、近似するための端数は、２つ以上の知られているフィルタの平均を使用することによってのような、他の何らかの方法で発生させることができる。] 図１
[0019] 例えば、Ｊａｒｖｉｓ氏、Ｊｕｄｉｃｅ氏、および、Ｎｉｎｋｅ氏によって作成されたフィルタ（“Ｊａｒｖｉｓ−Ｊｕｄｉｃｅ−Ｎｉｎｋｅフィルタ”、または、“Ｊａｒｖｉｓフィルタ”）を、表３に示した。]
[0020] このフィルタは、Ｓｔｕｃｋｉフィルタと同じ位置において重みを持つが、重みは、異なる端数である。これらのフィルタの重みの間の中間点をとることができ、結果としての端数を、２進分数で近似することになる重みとして使用できる。（例えば、“＊”ピクセルの右のピクセルに対して、その位置において使用するＳｔｕｃｋｉフィルタおよびＪａｒｖｉｓフィルタの端数の算術平均−［（７／４８）＋（８／４２）÷２＝１１３／６７２］−を使用でき、次に、この新しい端数を２進分数で近似する。）
１０４において、加算、減算、および、左シフトのシーケンスとして、重み中の分子を計算するためのアルゴリズムを見つける。このようなアルゴリズムを見つけるための例示的なプロセスを、以下で図４−６と表５に関連して説明する。] 図４
[0021] １０６において、あるピクセルに関係するカラー誤差を計算する。したがって、あるピクセルのオリジナルのカラーが、利用可能なカラーパレット中のカラーへと丸められている場合、丸め誤差が発生する。この丸め誤差は、１０６において計算される。]
[0022] １０８において、１０４において見つけられたアルゴリズムを、拡散ディザリングプロセスにおいて使用して、１つのピクセルから他のピクセルへと誤差を分配する。したがって、Δが、ソース画像中のカラー値を、利用可能なカラーパレット中のカラー値へと丸めることに関係する誤差である場合、そして、Ｗkが、その誤差に適用されることになるフィルタからの２進分数中の分子である場合、一連の左シフト、加算、および、減算として、Ｗk・Δを計算するためのアルゴリズムが、その積を見つけるために適用される。]
[0023] １１０において、累積された誤差値が、フィルタにおいて使用される分母によって除算される。したがって、フィルタは、その分母が２の累乗である端数を使用するように選ばれているので、この除算は、右シフト演算を使用して実行できる。]
[0024] １１２において、１１０において計算された値が、適用されているフィルタにしたがって、ピクセルに分配される。]
[0025] 重みを計算するためのアルゴリズムを見つけることは、計算集約的である。したがって、ステージ１０２および１０４は、より低い計算パワーを備える機械上で実行される効率的なアルゴリズムを発生させるために、通常は、高い計算パワーを備える機械上で実行されるだろう。アルゴリズムが発生された後、ステージ１０６−１１２は、発生されたアルゴリズムを使用して、異なる機械（例えば、ワイヤレス電話機、ハンドヘルドコンピュータ等）上で実行されることができる。しかしながら、ステージ１０２−１１２は、何らかの環境において、および、何らかのタイプの機械上で実行されることができる。]
[0026] 図２は、フィルタ中で重みを近似する２進分数を計算する例示的なプロセス２００を示す。プロセス２００は、図１中のステージ１０２を実行するための例示的な方法である。近似されることになるフィルタは、既存のフィルタ（例えば、Ｓｔｕｃｋｉフィルタ、Ｊａｒｖｉｓフィルタ等）であってもよく、既存のフィルタの平均（例えば、Ｓｔｕｃｋｉフィルタ、Ｊａｒｖｉｓフィルタの重みの間の中間点）であってもよく、または、何らかの方法で選ぶことができてもよい。プロセス２００は、範囲２minから２max中の２の累乗である分子を持つフィルタの近似を発生させる。プロセス２００において、ａ、ｂ、および、ｋは、変数名である。２０２において、ｋは、最小値（ｍｉｎ）に等しくセットされる。例えば、ｍｉｎ＝２であり、ｍａｘ＝１０である場合、フィルタ重みの２進近似の計算は、その分母が２2（＝４）に等しい重みで開始することになり、一連の４，８，１６，・・・，１０２４を通して続くだろう。２０４において、ａがフィルタの第１の重みに等しくセットされる（例えば、Ｓｔｕｃｋｉフィルタにおける８／２４）。２０６において、ｂが、ａ×２kに等しくセットされ、次に、最も近い整数へと丸められる。最も近い整数へと丸めるための１つの方法は、ａ×２kに０．５を加算し、次に、フロア関数を使用して、次の最も低い整数へと端数量を切り詰めることである。しかしながら、何らかの丸めメカニズムを使用してもよい。] 図１ 図２
[0027] ２０８において、ｂの値が出力される。１つの例において、ｂの値は、現在の分母と、それが近似する比とともに出力される。したがって、プロセス２００が、現在、分母２6＝６４で近似を計算している場合（すなわち、ｋ＝６である場合）、そして、近似されている端数が、８／４２である場合、ｂは、206において計算されるように、１２に等しくなり、したがって、“１２／６４は、８／４２におよそ等しい”のような情報が、提供されることができる。しかしながら、ｂは、何らかの方法で２０８において出力されることができる。]
[0028] ２１０において、フィルタ中に別の重みがあるか否かが決定される。別の重みがある場合、ａは、次の重みに等しくセットされ、プロセス２００は２０６に戻って、次の重みの近似を計算する。２１０において、フィルタ中に別の重みがないとして決定される場合、（２１４において、）ｋはインクリメントされる。（２１６において決定されるように、）ｋが最大値（ｍａｘ）より大きい場合、プロセス２００は終了する。そうではない場合、プロセスは２０４に戻って、次のｋの値に基づいて、フィルタの近似を計算し始める。]
[0029] いったん、その重みが２進分数であるフィルタが見つかると、アルゴリズムが作成されて、左シフト、加算、および、減算の演算のシーケンスとして、端数を適用する。例えば、表４は、その重みが２進分数である例示的なフィルタを示す。]
[0030] 表４において、分子は、１、４、６、および１１である。この分母、６４が２の累乗であるように選ばれたので、６ビットだけ（６４＝２6）右シフトすることによって、除算が実行できる。したがって、これらの比を適用する際に効率的であるアルゴリズムを見つけるために、左シフト、加算、および、減算の演算を使用して、分子によって、誤差値を乗算するための方法に対するサーチが行われる。例えば、ｗnが、左シフト、加算、および、減算の演算を使用して、達成できる特定の値を表現する場合、以下は、１、４、６、および１１による乗算のためのアルゴリズムの一例である（ここで、“＜＜”は、左シフト演算を表し、したがって、ｘ＜＜ｙは、ｙビットだけ左シフトされたｘを意味する）。
Ｗ0 ＝１；
Ｗ1 ＝Ｗ0 ＜＜ ２； （＝４）
Ｗ2 ＝Ｗ0 ＋ Ｗ1； （＝５）
Ｗ3 ＝Ｗ0 ＋ Ｗ2； （＝６）
Ｗ4 ＝Ｗ2 ＋ Ｗ3； （＝１１）
したがって、Ｗ0の開始値があるとすると、このアルゴリズムは、左シフトと加算の演算を使用して、４、５、６、および、１１によって、どのように乗算するかを示す。このケースでは、５は、分子における値のうちの１つではないが、これは、他の値を計算するのに使用されることができる中間値である（例えば、Ｗ2＝５は、Ｗ4＝１１を計算するための数式中で出現する）。したがって、数を、例えば、６（＝Ｗ3）によって乗算するために、Ｗ0を、６によって乗算されることになる数に等しくセットすることができ、次に、上記の数式を、以下のように適用することができる：
Ｗ3 ＝Ｗ0 ＋Ｗ2
Ｗ3 ＝Ｗ0 ＋（Ｗ0 ＋Ｗ1）
Ｗ3 ＝Ｗ0 ＋（Ｗ0 ＋（Ｗ0 ＜＜２））
したがって、例えば、９×６を乗算するために、Ｗ0は、９に等しくセットされ、Ｗ3に対する解は以下のような積である：
Ｗ3 ＝９＋（９＋（９＜＜２））
Ｗ3 ＝９＋（９＋（３６））
Ｗ3 ＝５４
これは、９×６に対する解である。解は、２つの加算演算と、１つのシフト演算とを使用して計算される。]
[0031] アルゴリズムの複雑さは、その従属性のグラフとしてモデル化することができる。図３は、上記のアルゴリズムにおける従属性のグラフを示す。図３のグラフは、係数Ｗ0からＷ4に対応する、ノード３００、３０１、３０２、３０３、および、３０４を持つ。グラフは、各ノードの、他のノードへの従属性を示す。したがって、ノード３００（Ｗ0）は、システムのベース値であり、他の何らかのノードの値からの計算に依拠していない。（“ＮＯＰ”は、“演算なし（ｎｏ ｏｐｅｒａｔｉｏｎ）”を意味し、ベースノード３００は、他のノードでの演算を実行することなく発生されることを示している。）ノード３０１（Ｗ1）は、ノード３００に依存しており、ノード３００の値に、左シフト演算（“ＳＨＬ”）を実行することによって、取得される。ノード３０２（Ｗ2）は、ノード３０１の値とノード３００の値に、加算演算（“ＡＤＤ”）を実行することによって、取得される。このように、ノード３０４まで同様である。グラフから、グラフ中の最も中心から離れたノードであるノード３０４が、ノード３００−３０３の値に、直接または間接的に依存していることが分かる。したがって、ノード３０４における値は、ノード３０１、３０２、および、３０３において、値を計算（１つのシフトと２つの加算を含む）することと、次に、ノード３０２と３０３をオペランドとして、追加の加算演算を実行することによって、取得される。したがって、アルゴリズム中の最も複雑な計算は、３つの加算演算と、１つのシフト演算を含む。] 図３
[0032] アルゴリズムを見つけるために、ある者は、計算できることを望む係数、例えば、上記のフィルタにおける分子１、４、６、および１１、から開始してもよい。次に、これらの係数を導く計算に対するサーチを実行する。係数のフルセットに対する計算がみつけられた後、これらの計算は、アルゴリズムとして集合される。アルゴリズムの複雑さが、これらの係数を生み出す、他の知られているアルゴリズムに対して比較される。複雑さは、例えば、係数のうちの１つに到達するために使用される最長パス中に、どれほど多くの演算があるかに基づいて、決定されてもよい。あるいは、複雑さは、加算演算、もしくは、シフト演算の数における個別の制限、または、シフトされることになるビットの数への制限のような、より特定化された基準に基づいていてもよい。各アルゴリズムは、捜される係数のフルセットと、潜在的にこれらの計算において使用される中間値を生み出すための公式を含んでいてもよい（上でＷ0からＷ4に対して記述したもののような）１組の計算である。]
[0033] アルゴリズムをサーチするプロセスの一部として、“ディクショナリ”が作成され、ディクショナリは、さまざまな値を発生させるのに使用できる演算のカレントスタックを記憶する。ディクショナリは、１のベース値から開始し、拡張プロセスを使用して、ディクショナリに対して演算を加えて、捜されている係数を生み出す。拡張プロセスの議論に移る前に、ディクショナリとそのデータ構造を最初に説明する。ディクショナリは、配列として表現でき、配列中の各エレメントは、特定の値を含み、現在の値に到達するように、ディクショナリ中の他の値の関数として実行される演算もまた含む。図４は、配列４５０を示し、これは複数のエレメントを含む。図４に示した配列の例示的な状態において、配列４５０は、上に記述した例における係数Ｗ0、Ｗ1、および、Ｗ2を表す、３つのエレメント４００、４０１、および４０２を有する。] 図４
[0034] エレメント４００は、係数Ｗ0に対応する。これは、演算“ＮＯＰ”を実行することによって取得される１の値を持つ。（“ＮＯＰ”は、“演算なし（ｎｏ ｏｐｅｒａｔｉｏｎ）”を表し、すなわち、Ｗ0は他の値がそれに基づくベース値であるので、他のエレメント上に演算を実行することなく、Ｗ0が取得されることを示している。）エレメント４００において、“ｌｐｌ”は、そのエレメントによって表現される係数を導く“最も長いパス長”を表し、これは、エレメント４００に対してゼロに等しく、これは、Ｗ0はシステムのベース値であり、それに到達するのに何のパスも使用されないためである。“ｎｃｏｎｎ”は、他のエレメントに対するそのエレメントからの“接続の数”を表す。引き続いて説明するように、エレメント４００を使用して、エレメント４０１および４０２を計算し、したがって、エレメント４００中のｎｃｏｎｎは、２に等しく、エレメント４００に依拠する、他の２つのエレメントがあるという事実を表す。（図３に示したグラフにおいて、あるノードの“ｎｃｏｎｎ”値は、そのノードから導かれるエッジの数に対応する。）
エレメント４０１は、係数Ｗ1に対応し、４の値を持つ。エレメント４０１における“ｏｐ”フィールドは、“ＳＨＬ”（“左シフト”）に等しい。エレメント４０１は、“ｉ＝０”の値を持ち、配列４５０中の０番目のエレメント（エレメント４００）が、演算のオペランドであることを意味している。エレメント４０１はまた、値“ｓ＝２”を持ち、エレメント４０１の値を生み出すために、オペランドの値がシフトされることになるビット数を表している。エレメント４０１は、１に等しい“ｌｐｌ”値を持ち、ベースエレメント４００から、エレメント４０１に対して導く演算パスの長さは１、すなわち、１つのシフト演算であることを表している。エレメント４０１はまた、１に等しい“ｎｃｏｎｎ”値を持ち、エレメント４０１の値に依拠する他の１つのエレメントがあることを表している。（この例では、エレメント４０２はエレメント４０１に依拠している。）
エレメント４０２は、係数Ｗ2に対応し、５の値を持つ。エレメント４０２における“ｏｐ”フィールドは、“ＡＤＤ”（他の２つのエレメントの間の加算）に等しい。エレメント４０２は、“ｉ＝０”、および“ｊ＝１”の値を持ち、配列４５０中の０番目と１番目のエレメント（エレメント４００と４０１）が、“ＡＤＤ”演算のオペランドであることを意味している。エレメント４０２の値は、エレメント４００と４０１の値を加算することによって、取得される。エレメント４０２は、２に等しい“ｌｐｌ”値を持ち、ベースエレメント４００から、エレメント４０２に到達するのに、２つの演算が使用されることを表している。（すなわち、エレメント４００からエレメント４０１を計算するのに使用されるＳＨＬ演算と、エレメント４００と４０１の値からエレメント４０２を計算するのに使用されるＡＤＤ演算とである。）エレメント４０２は、０に等しい“ｎｃｏｎｎ”値を持ち、エレメント４０２が、グラフ中のリーフであることを意味し、それらの値を計算するために、エレメント４０２において計算された値に依拠する、他の何のエレメントもないことを表している。] 図３
[0035] 図５は、図４の配列４５０中のエレメントに対して使用されてもよい例示的なデータ構造５００を示す。データ構造５００は、値フィールド５０２、演算子フィールド５０４、第１のインデックスフィールド５０６、第２のインデックスフィールド５０８、シフト演算においてシフトするビットの数を記憶するフィールド５１０、最も長いパス長（“ｌｐｌ”）値を記憶するフィールド５１２、および、接続の数（“ｎｃｏｎｎ”）値を記憶するフィールド５１４を含む。データ構造５００の各インスタンスは、係数を表し、これは、フィルタを実現するのにサーチされる係数であってもよく、中間値であってもよい。] 図４ 図５
[0036] フィールド５０２は、エレメントによって表現される係数の値を記憶する。例えば、エレメントが、ベース係数Ｗ0を表す場合、そのエレメント中の値は１であるだろう。]
[0037] フィールド５０４は、他のエレメントからエレメント値を達成するのに使用される演算子を記憶する。例えば、フィールド５０４は、“ＳＨＬ”（左シフト）、“ＡＤＤ”（加算）、“ＳＵＢ”（減算）、および、“ＮＯＰ”（演算なし）のような値を記憶できる。これらの演算は、例えば、異なる整数によってデータ構造５００中で表現されてもよく、象徴的に、名称“ＳＨＬ”、“ＡＤＤ”、“ＳＵＢ”、および、“ＮＯＰ”に関係付けられることができる。ＮＯＰは、プレースホルダー演算であり、これは、他の何らかのエレメント上での演算を実行することなく、そのエレメントが導出されることを意味する。ＮＯＰ演算は、配列中の第１のエレメントに対して使用され、これは、Ｗ0（＝１）のベース値であり、ここから、配列中の他のエレメントが、直接的に、または、間接的に導出される。]
[0038] フィールド５０６および５０８は、所定の演算のオペランドのインデックスを、ディクショナリ配列へと記憶する。例えば、ＡＤＤおよびＳＵＢ演算は、２つのオペランドをとり、フィールド５０６および５０８の両方は、ＡＤＤまたはＳＵＢ演算に対して規定された値を持つだろう。フィールド５０６および５０８が、値ｍおよびｎを持ち、フィールド５０４は、値ＡＤＤを持つ場合、このシナリオは、配列中の現在のエレメントは、ｍ番目のエレメントと、ｎ番目のエレメントを加算することによって計算されることを意味する。]
[0039] ＳＨＬ演算は、１つのオペランドをとり、したがって、フィールド５０４が値ＳＨＬを持つケースでは、フィールド５０６は、オペランドのインデックスを記憶でき、フィールド５０８は、ブランクのままにされてもよい。フィールド５０４が値ＳＨＬを持つケースでは、シフトされることになるビット数は、フィールド５１０中に記憶される。したがって、フィールド５０４が値ＳＨＬを持ち、フィールド５０６が値ｍを持ち、フィールド５１０が値ｎを持つ場合、このシナリオは、配列中の現在のエレメントが、ｍ番目のエレメントの値を、配列ｎビットだけ左シフトすることによって計算されることを意味する。]
[0040] フィールド５１２は、ベースエレメント（Ｗ0）からエレメントに到達するのに係るパスの長さを記憶する。このフィールドは、上で説明した“ｌｐｌ”値を保持する。したがって、現在のエレメントがベースエレメントである場合、Ｗ0からＷ0に到達するのに何の演算もとられないので、フィールド５１２の値はゼロである。他のエレメントに対して、フィールド５１２の値は、エレメントのオペランド中の“ｌｐｌ”値よりも１大きくセットされる。（または、単一のオペランドを持つＳＨＬ演算のケースでは、エレメントのオペランド中の“ｌｐｌ”値よりも１大きくセットされる。）
フィールド５１４は、エレメントが持つ外向きの接続の数を記憶し、すなわち、現在のエレメントをオペランドとして使用する、他のエレメントの数を記憶する。このフィールドは、上で説明した“ｎｃｏｎｎ”値であり、アルゴリズムに対するサーチの間に、ブックキーピングのために使用されて、リーフ、すなわち、グラフ中の“子を持たないノード”を表すエレメントを決定する。]
[0041] データ構造５００のインスタンスの配列を含むディクショナリは、到達可能な、知られている係数を表す。配列が、サーチされているすべての係数を持つエレメントを含むとき、配列の内容は、これらの係数を発生させるアルゴリズムを含む。したがって、これらの係数を発生させるアルゴリズムを見つけるために、配列中のゼロ番目のエレメントを、１の値を持つように、セットすることによって、配列がベースエレメント（Ｗ0）で初期化される。次に、演算のさまざまな組み合わせを通して到達されるさまざまな値で、配列が埋められる。配列が、サーチされている係数を含む状態に到達したとき、配列のコンテンツがキャプチャされる。キャプチャされたコンテンツは、アルゴリズムとして保存できる。または、アルゴリズムの効率性が、従前に発見されたアルゴリズムに比較でき、そのアルゴリズムが従前のアルゴリズムより効率的である場合、そのアルゴリズムが保存できる。１つ以上のアルゴリズムが発生された後、ディザリングフィルタ中の係数を計算するために、アルゴリズムのうちの１つを選択できる。]
[0042] 図６は、アルゴリズムを発生させる例示的なプロセスのフロー図である。６０２において、発生されることになる１組の係数が受け取られる。６０４において、ディクショナリが、その値が１である、ベースエントリ（Ｗ0）を持つように初期化され、そのオペランドとしてディクショナリ中に他のエレメントを持たない。６０６において、リカージョンを実行して、ディクショナリに対する新しい値と演算を発生させ、６０２において受信された係数を発生させるアルゴリズムを保存する。ディクショナリを埋める再帰的方法の例は、以下に擬似コードにおいて説明する。６０８において、リカージョンによって発見されたアルゴリズムが出力される。] 図６
[0043] 表５は、ディクショナリに対する新しい値と演算を発生させるのに使用できる、例示的なリカージョンの擬似コードを示す。例示的なリカージョンは、ディクショナリ上で、あるパラメータで、演算のすべての組み合わせを試行する点で、“網羅的な”サーチとして見られることができるサーチを実行する。しかしながら、アルゴリズムに対するサーチは、以下に示すアルゴリズムによって実行される必要はなく、このような方法が“網羅的”であるか否かに関わらず、何らかの方法で実行されることができる。]
[0044] ［表５］
Function expand（）｛
／＊ try shift ＊／
for each entry i in the dictionary｛
for k = 1 to （max bit length - msb _ position _ of（i．value）） ｛
try adding new entries that shift the i.value to the left by k bits;
if entry duplicates a value that is already in the dictionary then
remove the top entry;
else if the dictionary still does not have all the values sought then｛
expand（）; ／／ continue trying to find the next value
remove the top entry; ／／ unwind the stack after returning from the recursion
｝
else｛ ／／ dictionary has all the factors being sought
if the current algorithm is at least as efficient as the saved algorithms then｛
save the current contents of the dictionary as a new algorithm;
remove the top entry;
｝
｝
｝
｝
／＊ try adds＊／
for each pair （i，j) of entries in the dictionary, where i ≠ j｛
try adding new entries that are the sum of i.value ＋ j. value;
if entry duplicates a value that is already in the dictionary then
remove the top entry;
else if the dictionary still does not have all the values sought then｛
expand（）; ／／ continue trying to find the next value
remove the top entry; ／／ unwind the stack after returning from the recursion
}
else｛ ／／ dictionary has all the factors being sought
if the current algorithm is at least as efficient as the saved algorithms then｛
save the current dictionary as a new algorithm;
remove the top entry;
｝
｝
｝
／＊ try subtracts ＊／
／／ Similar to "try adds", but tries to add element that subtract one existing element
／／ from anotherinstead of adding two existing elements
｝]
[0045] 表５のｅｘｐａｎｄ（）関数は、既存のエントリに基づいて、新しい演算を追加することによって、ディクショナリを拡張しようとする。図６（６０４において）述べたように、ディクショナリは、その値が１であるベースエントリを持つように初期化され、これは、演算するための１つのエントリを与えることによって、表５のｅｘｐａｎｄ（）関数を“ブートストラップする”。次に、辞書の任意の状態があるとして、ｅｘｐａｎｄ（）関数は、以下のようにすることによって、ディクショナリに対して、新しいエントリを加えようとする：すなわち、
・ディクショナリ中の各エントリに対して、ｅｘｐａｎｄ（）は、エントリを左シフトする新しい演算を加えようとする。したがって、ディクショナリ中に、１の値を持つエントリがある場合、ｅｘｐａｎｄ（）は、その値を、１，２，３，・・・ビットだけ、左にシフトする演算を加えようとする。捜されている値の“最大ビット長ｍａｘ＿ｂｉｔ＿ｌｅｎｇｔｈ”があるかもしれず（例えば、プロセスは、１０、または、より少ない最上位ビットを持つ値に対してルックするようにセットされていてもよく）、ｆｏｒループ条件“ｋ＝１ ｔｏ （ｍａｘ＿ｂｉｔ＿ｌｅｎｇｔｈ − ｍｓｂ＿ｐｏｓｉｔｉｏｎ＿ｏｆ（ｉ．ｖａｌｕｅ））”は、ｅｘｐａｎｄ（）が“最大ビット長 ｍａｘ＿ｂｉｔ＿ｌｅｎｇｔｈ”を超えて、確実に、最上位ビットをシフトしないようにする。
・ディクショナリの各個別のエントリ対に対して、ｅｘｐａｎｄ（）は、エントリ対中の値を加算する新しい演算を加えようとする。
・ディクショナリの各個別のエントリ対に対して、ｅｘｐａｎｄ（）は、１つのエントリ中の値を、もう１つのエントリの値から、減算する新しい演算を加えようとする。
新しいエントリを追加するための試みが行われた後、ｅｘｐａｎｄ（）は、さまざまなテストを実行する：すなわち、
・追加されたエントリが、ディクショナリ中に既に見られる値を複製する場合、ディクショナリが、同じ値に対する２つの別個のパスを含まないように、追加されたエントリは除去される。（追加されたエントリが、ディクショナリの“トップ”にあるので、この除去は、トップエントリを除去することによって達成される。）
・追加されたエントリが、既存の値を複製しない場合、ディクショナリエントリ中の１組の値が、捜されている１組の係数に比較される。エントリの追加後に、ディクショナリがまだ、捜されているすべての係数を含んでいない場合、ｅｘｐａｎｄ（）は、それ自身を再帰的に呼び出し、ディクショナリにより多くの値を追加する。再帰的な呼出の後で、ｅｘｐａｎｄ（）は、再帰的呼出の前に追加されたエントリを除去する。この除去は、ディクショナリによって、表現される演算のスタックを、再帰的呼出が戻るにつれて、アンワインドさせる。
・追加された新しい値が、捜されている全ての係数をディクショナリが含むことにさせる場合、ｅｘｐａｎｄ（）は、ディクショナリの現在の状態が、新しいアルゴリズムとして保存されることになるか、否かを決定する。ｅｘｐａｎｄ（）は、現在のアルゴリズムが、既に保存されている、他のアルゴリズムと少なくとも同じくらい効率的であるか否かを決定する。（他のアルゴリズムが何もない場合、現在のアルゴリズムは、最も効率的であるとされ、保存される。）効率性は、何らかの値に到達するのにアルゴリズムが使用する最長パス長（すなわち、演算の数）を決定することのような、さまざまなアルゴリズム基準によって決定できる。] 図６
[0046] 以下は、ここで主題が配備されてもよい例示的な環境の説明である。]
[0047] 図７を参照して、ハンドセットのような、ワイヤレスデバイスまたは端末７００の、潜在的な構成の概念ブロック図を図示する。当業者が理解することになるように、端末７００の構成は、特定のアプリケーション、全体の設計制約等のような要因に依拠して、異なっていてもよい。プロセッサ７０２は、ここで開示するシステムと方法を実現できる。] 図７
[0048] 端末７００は、アンテナ７０６に結合されたフロントエンドトランシーバ７０４とともに実現されることができる。フロントエンドトランシーバ７０４は、データ通信を受信するように構成されている。ベースバンドプロセッサ７０８は、トランシーバ７０４に結合されることができる。ベースバンドプロセッサ７０８は、ソフトウェアベースのアーキテクチャ、または、他のタイプのアーキテクチャで実現されることができる。他の機能のうちでも、制御と全体のシステム管理機能を提供する、ソフトウェアプログラムを実行するときにマイクロプロセッサを利用できる。デジタルシグナルプロセッサ（“ＤＳＰ”）組み込み通信ソフトウェアレイヤで実現されることができ、これは、アプリケーション特有のアルゴリズムを実行して、マイクロプロセッサ上での処理要求を減少させる。ＤＳＰを利用して、パイロット信号捕捉、時間同期、周波数追跡、拡散スペクトラム処理、変調と復調機能、フォワードエラー訂正のような、さまざまな信号処理機能を提供できる。]
[0049] 端末７００はまた、ベースバンドプロセッサ７０８に結合された、さまざまなユーザインターフェース７１０も含むことができる。ユーザインターフェース７１０は、キーパッド、マウス、タッチスクリーン、ディスプレイ、リンガー、バイブレータ、オーディオスピーカ、マイクロフォン、カメラ、および／または、他の入力出力デバイスを含むことができる。]
[0050] ベースバンドプロセッサ７０８は、プロセッサ７０２を含む。ベースバンドプロセッサ７０８のソフトウェアベースの実現では、プロセッサ７０２は、マイクロプロセッサ上で実行されているソフトウェアプログラムであってもよい。しかしながら、プロセッサ７０２は、この実現に制限されておらず、ここで記述したさまざまな機能を実行することができる、ハードウェア構成、ソフトウェア構成、または、これらの組み合わせを含む、技術的に知られているさまざまな手段によって実現されてもよい。プロセッサ７０２は、データ記憶のためにメモリ７１２に結合されることができる。メモリ７１２は、製造および／またはテストプロセスの間に受信されたプログラムデータを記憶するように構成されており、プロセッサ７０２または７０８は、プログラムデータでプログラムされるように構成されている。]
[0051] ここで説明する実施形態は、ハードウェア、ソフトウェア、フォームウェア、ミドルウェア、マイクロコード、または、これらの任意の組み合わせによって実現されてもよい。システムおよび／または方法が、ソフトウェア、フォームウェア、ミドルウェア、または、マイクロコード、プログラムコードもしくはコードセグメントにおいて実現されるとき、これらは、ストレージコンポーネントのような機械読取可能媒体中に記憶されてもよい。コードセグメントは、手続、関数、サブプログラム、プログラム、ルーチン、サブルーチン、モジュール、ソフトウェアパッケージ、クラス、または、命令、データ構造、もしくは、プログラムセグメントの何らかの組み合わせを表してもよい。コードセグメントは、情報、データ、引数、パラメータ、または、メモリコンテンツを送ることおよび／または受け取ることによって、別のコードセグメント、または、ハードウェア回路に結合されてもよい。情報、引数、パラメータ、データ等は、メモリ共有、メッセージ送信、トークンパッシング、ネットワーク送信等を含む任意の適切な手段を使用して、送出されてもよく、送られてもよく、送信されてもよい。]
[0052] ソフトウェア実現に関しては、ここで説明した技術を、ここで説明した機能を実行するモジュール（例えば、手続、関数等）で実現してもよい。ソフトウェアコードは、メモリユニット中に記憶されてもよく、プロセッサによって実行されてもよい。メモリユニットは、プロセッサ内で実現されてもよく、または、プロセッサ外部で実現されてもよい。外部のケースでは、メモリユニットは、技術的に知られているさまざまな手段を通してプロセッサに通信可能に結合されることができる。]
[0053] ここで開示した実施形態と関連して述べた方法またはアルゴリズムのステージを、直接、ハードウェアで、プロセッサにより実行されるソフトウェアモジュールで、あるいは、２つの組み合わせで具体化してもよい。ソフトウェアモジュールは、ランダムアクセスメモリ（“ＲＡＭ”）メモリ、フラッシュメモリ、読出専用メモリ（“ＲＯＭ”）メモリ、消去可能プログラム可能ＲＯＭ（“ＥＰＲＯＭ”）メモリ、電気的消去可能プログラム可能ＲＯＭ（“ＥＥＰＲＯＭ”）メモリ、レジスタ、ハードディスク、リムーブバルディスク、ＣＤ−ＲＯＭ、あるいは、技術的に知られている他の何らかの形態の記憶媒体に存在していてもよい。例示的な記憶媒体は、プロセッサが記憶媒体から情報を読み取り、記憶媒体に情報を書き込むことができるようにプロセッサに結合される。代替実施形態では、記憶媒体はプロセッサと一体化されてもよい。プロセッサおよび記憶媒体は、ＡＳＩＣに存在してもよい。ＡＳＩＣはユーザ端末に存在してもよい。代替実施形態では、プロセッサおよび記憶媒体は、ユーザ端末中のディスクリートコンポーネントとして存在してもよい。]
[0054] ここで説明した方法は、当業者のうちの１人によって知られている、さまざまなハードウェア、プロセッサ、および、システム上で実現されてもよいことに留意すべきである。例えば、実現において使用される機械は、コンテンツと情報を表示するディスプレイ、クライアントの動作を制御するプロセッサ、および、機械の動作に関係するデータとプログラムを記憶するメモリを有していてもよい。何らかの実現では、機械はセルラ電話機である。何らかの実現では、機械は手持ちコンピュータ、または、通信能力を有するハンドセットである。別の実現では、機械は、通信能力を有するパーソナルコンピュータである。]
[0055] ここで説明する実施形態に関連して説明する、さまざまな例示的なロジックブロック、モジュール、回路、エレメント、および／または、コンポーネントは、汎用プロセッサ、ＤＳＰ、ＡＳＩＣ、フィールドプログラム可能ゲートアレイ（ＦＰＧＡ）または他のプログラム可能ロジックデバイス、ディスクリートゲートまたはトランジスタロジック、ディスクリートハードウェア構成部品、あるいは、ここで説明する機能を実現するように設計されているこれらの任意の組み合わせとともに実現、または、実行してもよい。汎用プロセッサは、マイクロプロセッサであってもよいが、代わりに、プロセッサは、任意の従来のプロセッサ、制御装置、マイクロ制御装置、または、状態機械であってもよい。プロセッサはまた、計算デバイスの組み合わせとして、例えば、ＤＳＰとマイクロプロセッサの組み合わせ、複数のマイクロプロセッサ、ＤＳＰコアと連携した１つ以上のマイクロプロセッサ、または、他の何らかのこのような構成として、実現されてもよい。]
[0056] 主題を構造的な特徴および／または方法的動作に特有の言語において説明してきたが、特許請求の範囲において規定する主題は、上に説明する特定の特徴または動作に限定される必要はないことが理解されるだろう。むしろ、上に説明した特定の特徴と動作は、特許請求の範囲を実現する例示的な形態として開示した。]

权利要求:

請求項1
画像を処理する方法において、画像中の第１のピクセルのカラーと、前記カラーに基づいてカラーパレットから選択されたカラー値との間の差に基づいて、誤差を計算することと、１つ以上のシフト、加算、または、減算の演算、あるいは、これらの組み合わせを使用することによって、前記誤差と、フィルタ中の複数の重みのそれぞれとの第１の積を計算することと、前記フィルタにしたがって、複数の第２のピクセルに対して、前記第１の積を分配することとを含み、前記複数の重みのそれぞれは２進分数である方法。
請求項2
前記重みのそれぞれは、分子と分母によって表現され、前記誤差と、前記重みのそれぞれとの前記第１の積の前記計算は、前記分子のそれぞれと、前記誤差との第２の積を計算することと、前記第２の積と、前記分母とに基づいて商を計算することとを含む、請求項１記載の方法。
請求項3
前記第２の積の前記計算は、乗算命令を使用することなく、シフト、加算、および、減算の演算を使用して実行される、請求項２記載の方法。
請求項4
前記商の前記計算は、除算命令を使用することなく、前記第２の積への右シフト演算を使用して実行される、請求項２記載の方法。
請求項5
前記フィルタ中の重みは、Ｆｌｏｙｄ−Ｓｔｅｉｎｂｅｒｇフィルタ、Ｊａｒｖｉｓ−Ｊｕｄｉｃｅ−Ｎｉｎｋｅフィルタ、Ｓｔｕｃｋｉフィルタ、Ｂｕｒｋｅｓフィルタ、または、Ｓｉｅｒｒａ３フィルタから導出される重みを近似する２進分数である、請求項１記載の方法。
請求項6
画像を処理する方法を実行するための実行可能命令を備える１つ以上のコンピュータ読取可能媒体において、前記方法は、画像中の第１のピクセルのカラーと、前記カラーに基づいてカラーパレットから選択されたカラー値との間の差に基づいて、誤差を計算することと、１つ以上のシフト、加算、または、減算の演算、あるいは、これらの組み合わせを使用することによって、前記誤差と、フィルタ中の複数の重みのそれぞれとの第１の積を計算することと、前記フィルタにしたがって、複数の第２のピクセルに対して、前記第１の積を分配することとを含み、前記複数の重みのそれぞれは２進分数である、１つ以上のコンピュータ読取可能媒体。
請求項7
前記重みのそれぞれは、分子と分母によって表現され、前記誤差と、前記重みのそれぞれとの前記第１の積の前記計算は、前記分子のそれぞれと、前記誤差との第２の積を計算することと、前記第２の積と、前記分母とに基づいて商を計算することとを含む、請求項６記載の１つ以上のコンピュータ読取可能媒体。
請求項8
前記第２の積の前記計算は、乗算命令を使用することなく、シフト、加算、および、減算の演算を使用して実行される、請求項７記載の１つ以上のコンピュータ読取可能媒体。
請求項9
前記商の前記計算は、除算命令を使用することなく、前記第２の積への右シフト演算を使用して実行される、請求項７記載の１つ以上のコンピュータ読取可能媒体。
請求項10
画像を処理する装置において、画像を受信するインターフェースと、少なくとも１つのプロセッサと、前記プロセッサに結合され、または、前記プロセッサと一体化されているメモリとを具備し、前記少なくとも１つのプロセッサは、ロジックを実行して、画像中の第１のピクセルのカラーと、前記カラーに基づいてカラーパレットから選択されたカラー値との間の差に基づいて、誤差を計算し、１つ以上のシフト、加算、または、減算の演算、あるいは、これらの組み合わせを使用することによって、前記誤差と、フィルタ中の複数の重みのそれぞれとの第１の積を計算し、前記フィルタにしたがって、複数の第２のピクセルに対して、前記第１の積を分配し、前記複数の重みのそれぞれは２進分数であり、前記ロジックは、前記メモリ中に記憶されている装置。
請求項11
前記重みのそれぞれは、分子と分母によって表現され、前記ロジックは、前記分子のそれぞれと、前記誤差との第２の積を計算することと、前記第２の積と、前記分母とに基づいて商を計算することとによって、前記誤差と、前記重みのそれぞれとの前記第１の積を計算する、請求項１０記載の装置。
請求項12
前記ロジックは、乗算命令ではなく、シフト、加算、および、減算の演算を使用して、前記第２の積を計算する、請求項１１記載の装置。
請求項13
前記ロジックは、前記第２の積への、除算命令ではなく、右シフト演算を使用して、前記商を計算する、請求項１１記載の装置。
請求項14
前記フィルタ中の重みは、Ｆｌｏｙｄ−Ｓｔｅｉｎｂｅｒｇフィルタ、Ｊａｒｖｉｓ−Ｊｕｄｉｃｅ−Ｎｉｎｋｅフィルタ、Ｓｔｕｃｋｉフィルタ、Ｂｕｒｋｅｓフィルタ、または、Ｓｉｅｒｒａ３フィルタから導出される重みを近似する２進分数である、請求項１０記載の装置。
請求項15
前記装置はハンドセットである、請求項１０記載の装置。
請求項16
前記装置は集積回路である、請求項１０記載の装置。
請求項17
画像を処理する装置において、画像中の第１のピクセルのカラーと、前記カラーに基づいてカラーパレットから選択されたカラー値との間の差に基づいて、誤差を計算する手段と、１つ以上のシフト、加算、または、減算の演算、あるいは、これらの組み合わせを使用することによって、前記誤差と、フィルタ中の複数の重みのそれぞれとの第１の積を計算する手段と、前記フィルタにしたがって、複数の第２のピクセルに対して、前記第１の積を分配する手段とを具備し、前記複数の重みのそれぞれは２進分数である装置。
請求項18
前記重みのそれぞれは、分子と分母によって表現され、前記誤差と、前記重みのそれぞれとの前記第１の積を計算する前記手段は、前記分子のそれぞれと、前記誤差との第２の積を計算する手段と、前記第２の積と、前記分母とに基づいて商を計算する手段とを備える、請求項１７記載の装置。
請求項19
前記第２の積を計算する前記手段は、シフト、加算、および、減算の演算を実行する手段を備える、請求項１８記載の装置。
請求項20
前記商を計算する前記手段は、前記第２の積への右シフト演算を実行する手段を備える、請求項１８記載の装置。
請求項21
ディザリング重みの計算を容易にする方法を実行する実行可能な命令を備える１つ以上のコンピュータ読取可能媒体において、前記方法は、複数の係数を受け取ることと、ベース値を有する第１のエレメントを含むように、配列を初期化することと、前記配列を、複数の第２のエレメントで埋めることと、１つ以上の基準に基づいて、前記配列のコンテンツが、１組の保存されているアルゴリズムに追加されることになるか、決定を行うこととを含み、前記複数の第２のエレメントは、それぞれ、（ａ）値と、（ｂ）前記値を導出するために、前記配列中の１つ以上の他のエレメント上で実行されることになる演算の表示とを含み、前記演算は、２つのエレメントの値を加算すること、１つのエレメントの値を別のエレメントから減算すること、または、１つのエレメントの値をあるビット数左シフトすることのうちのいずれかであり、前記１つ以上の基準は、前記係数のそれぞれが前記配列のエレメント中の値のうちに見つけられるという状態に前記配列があることを含む、コンピュータ読取可能媒体。
請求項22
前記１つ以上の基準は、前記配列が、前記１組の保存されているアルゴリズム中の、他の１つ以上のアルゴリズムに関して複雑さ基準を満たすアルゴリズムを表現していることをさらに含む、請求項２１記載のコンピュータ読取可能媒体。
請求項23
前記複雑さ基準は、前記配列が、前記係数の任意のものを計算するのに使用する演算の最大数は、前記保存されているアルゴリズムのうちの任意のものが、前記係数を計算するのに使用する係数の最大数より少なく、または、前記係数の最大数に等しいことを含む、請求項２１記載のコンピュータ読取可能媒体。
請求項24
前記埋めることは、前記配列中の既存のエレメント上の第１の演算を作成することと、前記第１の演算が、前記係数のうちにあるが、前記配列の他のエレメントのうちにない値を発生させるか、決定することと、前記第１の演算と、前記第１の演算からもたらされる値とを前記エレメント中に保存することと、少なくとも１つの終了条件下になるまで、前記作成、決定、および、保存を、再帰的に繰り返すこととを含む、請求項２１記載のコンピュータ読取可能媒体。
請求項25
前記係数はフィルタ中の重みであり、前記方法は、前記保存されているアルゴリズムのうちの１つを使用して、拡散ディザリングプロセス中で、ピクセル誤差に対して前記重みを適用することを含む、請求項２１記載のコンピュータ読取可能媒体。